<?php
/*
  Nested Set Tree Library
  
  Author:  Rolf Brugger, edutech
  URL:     http://www.edutech.ch/contribution/nstrees
  
  DB-Model by Joe Celko (http://www.celko.com/)
  
  References:
    http://www.sitepoint.com/article/1105/2
    http://searchdatabase.techtarget.com/tip/1,289483,sid13_gci537290,00.html
    http://dbforums.com/arch/57/2002/6/400142

    
 ------------------------------------------------------------------
 Modified by Michal Hantl (http://hantl.info) for my Cms purpouses.
 ==================================================================
  I recomend to download original Nested Set Tree Library instead
  of using this modyfied version.
  
  I do not take responsibility for any damage caused using or
  modyfying this class, so be careful;).
  
  Modifications
  -------------
  chopped some unuseful methods, enhanced comments, made 
  object-oriented, also code was beautyfied.
  
*/

class cNSTree
{
  function __construct(cCMS $cms, $lname="lft", $rname="rgt")
  {
    $this->l = $lname;
    $this->r = $rname;
    $this->t = $cms->tree->table;
    $this->cms = $cms;
  }
  
  /** Query */ 
  function q($q)
  {
  	return $this->cms->tree->query($q);
  }

  function newRoot ($newNode)
  /* creates a new root record and returns the node $this->l=1, $this->r=2. */
  {
    $newNode[$this->l] = 1;
    $newNode[$this->r] = 2;
    $this->_insertNew ($newNode);
    return $newNode;
  }

  function newFirstChild ($node, $newNode=array())
  /* creates a new first child of 'node'. */
  {
    $newNode[$this->l] = $node[$this->l]+1;
    $newNode[$this->r] = $node[$this->l]+2;
    $this->_shiftRLValues($newNode[$this->l], 2);
    $this->_insertNew ($newNode);
    return $newNode;
  }

  function newLastChild ($node, $newNode)
  /* creates a new last child of 'node'. */
  {
    $newNode[$this->l] = $node[$this->r];
    $newNode[$this->r] = $node[$this->r]+1;
    $this->_shiftRLValues($newNode[$this->l], 2);
    $this->_insertNew ($newNode);
    return $newNode;
  }

  function newPrevSibling ($node, $newNode)
  {
    $newNode[$this->l] = $node[$this->l];
    $newNode[$this->r] = $node[$this->l]+1;
    $this->_shiftRLValues($newNode[$this->l], 2);
    $this->_insertNew ($newNode, $newNode);
    return $newNode;
  }

  function newNextSibling ($node, $newNode)
  {
    $newNode[$this->l] = $node[$this->r]+1;
    $newNode[$this->r] = $node[$this->r]+2;
    $this->_shiftRLValues($newNode[$this->l], 2);
    $this->_insertNew ($newNode, $newNode);
    return $newNode;
  }


  /* ******************************************************************* */
  /* Tree Reorganization */
  /* all nstMove... functions return the new position of the moved subtree. */
  /* ******************************************************************* */
  
  /** moves the node '$src' and all its children (subtree) that it is the next sibling of '$dst'. */
  function MoveToNextSibling ($src, $dst)
  {
    return $this->_moveSubtree ($src, $dst[$this->r]+1);
  }
  
  /** moves the node '$src' and all its children (subtree) that it is the prev sibling of '$dst'. */
  function MoveToPrevSibling ($src, $dst)
  {
    return $this->_moveSubtree ($src, $dst[$this->l]);
  }
  
  /** moves the node '$src' and all its children (subtree) that it is the first child of '$dst'. */
  function MoveToFirstChild ($src, $dst)
  {
    return $this->_moveSubtree ($src, $dst[$this->l]+1);
  }
  
  /** moves the node '$src' and all its children (subtree) that it is the last child of '$dst'. */
  function MoveToLastChild ($src, $dst)
  {
    return $this->_moveSubtree ($src, $dst[$this->r]);
  }
  
  /** '$src' is the node/subtree, '$to' is its destination l-value */
  function _moveSubtree ($src, $to)
  { 
    $treesize = $src[$this->r]-$src[$this->l]+1;
    $this->_shiftRLValues($to, $treesize);
    if($src[$this->l] >= $to)
    { // src was shifted too?
  		$src[$this->l] += $treesize;
      	$src[$this->r] += $treesize;
    }
    /* now there's enough room next to target to move the subtree*/
    $newpos = 
    $this->_shiftRLRange($src[$this->l], $src[$this->r], $to-$src[$this->l]);
    /* correct values after source */
    $this->_shiftRLValues($src[$this->r]+1, -$treesize);
    if($src[$this->l] <= $to){ // dst was shifted too?
  	$newpos[$this->l] -= $treesize;
      $newpos[$this->r] -= $treesize;
    }  
    return $newpos;
  }
  
    /* -------------- internal routines ---------------- */
  
  /** adds '$delta' to all L and R values that are >= '$first'. '$delta' can also be negative. */
  function _shiftRLValues ($first, $delta)
  {
    $q1="UPDATE `".$this->t."` SET `".$this->l."`=".$this->l."+$delta WHERE ".$this->l.">=$first";
    $this->q($q1);
    $this->q("UPDATE `".$this->t."` SET `".$this->r."`=".$this->r."+$delta WHERE ".$this->r.">=$first");
  }

  /** adds '$delta' to all L and R values that are >= '$first' and <= '$last'. '$delta' can also be negative. returns the shifted first/last values as node array.  */
  function _shiftRLRange ($first, $last, $delta)
  {
    $this->q("UPDATE `".$this->t."` SET `".$this->l."`=".$this->l."+$delta WHERE ".$this->l.">=$first AND ".$this->l."<=$last");
    $this->q("UPDATE `".$this->t."` SET `".$this->r."`=".$this->r."+$delta WHERE ".$this->r.">=$first AND ".$this->r."<=$last");
    return array($this->l=>$first+$delta, $this->r=>$last+$delta);
  }
  
  /** creates a new root record and returns the node $this->l=1, $this->r=2. */
  function _insertNew ($node)
  {
    foreach ($node as $key=>$val) {
      $cols.="`$key`='$val',";
    }
    $cols=substr($cols,0,-1);
    $q="INSERT INTO `".$this->t."` SET $cols";
    $res = $this->q($q);
  }
  
  
  /* ******************************************************************* */
  /* Tree Destructors */
  /* ******************************************************************* */
  
  function delete ($node)
  /** deletes the node '$node' and all its children (subtree). */
  {
    $leftanchor = $node[$this->l];
    $this->q("DELETE FROM ".$this->t." WHERE ".$this->l.">=".$node[$this->l]." AND ".$this->r."<=".$node[$this->r]);
    $this->_shiftRLValues($node[$this->r]+1, $node[$this->l] - $node[$this->r] -1);
    return $this->GetNodeWhere($this->l."<".$leftanchor." ORDER BY ".$this->l." DESC");
  }

  /* returns the first node that matches the '$whereclause'. The WHERE-caluse can optionally contain ORDER BY or LIMIT clauses too. */  
  function getNodeWhere ($whereclause)
  {
  	$noderes[$this->l_field_name] = 0;
  	$noderes[$this->r_field_name] = 0;
  	$q="SELECT * FROM ".$this->table." WHERE ".$whereclause;
  	try {
  		$res = mysql_query($q);
		$noderes[$this->l_field_name] = $row[$this->l_field_name];
		$noderes[$this->r_field_name] = $row[$this->r_field_name];
  	} catch (Exception $e) {
		throw $e;
   	}
  	return $noderes;
  }

  
  /* Tree Functions
   * the following functions return a boolean value
   */
  
  /** only checks, if L-value < R-value (does no db-query)*/
  function ValidNode ($node)
  { 
  	return ($node[$this->l] < $node[$this->r]);
  }

  function HasAncestor ($node)
  { 
  	return $this->ValidNode(Ancestor($node));
  }

  function HasPrevSibling ($node)
  { 
  	return $this->ValidNode(PrevSibling($node));
  }

  function HasNextSibling ($node)
  { 
  	return $this->ValidNode(NextSibling($node));
  }

  function HasChildren ($node)
  { 
  	return (($node[$this->r]-$node[$this->l])>1);
  }

  function IsRoot ($node)
  { 
  	return ($node[$this->l]==1);
  }

  function IsLeaf ($node)
  { 
  	return (($node[$this->r]-$node[$this->l])==1);
  }

  /** returns true, if 'node1' is a direct child or in the subtree of 'node2' */
  function IsChild ($node1, $node2)
  { 
  	return (($node1[$this->l]>$node2[$this->l]) and ($node1[$this->r]<$node2[$this->r]));
  }

  function IsChildOrEqual ($node1, $node2)
  { 
  	return (($node1[$this->l]>=$node2[$this->l]) and ($node1[$this->r]<=$node2[$this->r]));
  }

  function Equal ($node1, $node2)
  { 
  	return (($node1[$this->l]==$node2[$this->l]) and ($node1[$this->r]==$node2[$this->r]));
  }
  
  
  function nbChildren ($node)
  { 
  	return (($node[$this->r]-$node[$this->l]-1)/2);
  }
  
  /** returns node level. (root level = 0)*/
  function level ($node)
  { 
    $res = $this->q("SELECT COUNT(*) AS level FROM ".$this->t." WHERE ".$this->l."<".($node[$this->l])." AND ".$this->r.">".($node[$this->r]));
    if ($row = mysql_fetch_array ($res)) {
      return $row["level"];
    } else {
      return 0;
    }
  }
  
}

?>